package arithmetic1.list;

/*
    环形链表来解决约瑟夫环的问题
 */
public class LoopLinkedList {
    //头节点
    private Node head;
    //尾指针
    private Node tail;

    public LoopLinkedList(Node head) {
        this.head = head;
        //尾指针默认指向头节点
        tail=head;
    }

    //添加一个元素
    public void add(Node node){
        //添加节点到最后
        tail.next=node;
        //尾指针后移
        tail=tail.next;
        //将该节点指向第一个节点
        node.next=head.next;
    }

//    //将从哪个节点开始的第几个节点弹出
//    public Node pop(Node startNode,int n){
//        //遍历到要删除节点的前一个节点
//        Node temp=startNode;
//        for (int i=1;i<n;i++){
//            temp=temp.next;
//        }
//        //记录要返回的节点，并删除
//        Node node=temp.next;
//        temp.next=temp.next.next;
//        if(n==1){
//            tail.next=node.next;
//        }
//        return node;
//    }
//
//    //约瑟夫环问题,从哪个节点开始，经过几个节点弹出
//    public void joseph(Node startNode,int n){
//        if(n<1){
//            System.out.println("不能小于1");
//            return;
//        }
//        if(startNode.next==null){
//            System.out.println("链表为空");
//            return;
//        }
//        Node node=pop(startNode,n);
//        System.out.print(node+"\t");
//        if(node.next==node){
//            return;
//        }
//        joseph(node,n);
//    }

    //从第几个节点开始，每经过几个节点弹出一个节点
    public void joseph(int startNo,int count){
        if(startNo<1 || head.next==null){
            System.out.println("参数非法或者链表为空");
            return;
        }
        //first指向第一个节点
        Node first=head.next;
        //将help指向最后
        Node help=tail;
        //将first指向开始位置,help指向first前一个位置
        for(int i=0;i<startNo-1;i++){
            first=first.next;
            help=help.next;
        }
        //将节点弹出,直到只有一个节点
        while (true){
            if(first==help){
                break;
            }
            //弹出一个节点
            for (int j=0;j<count-1;j++){
                first=first.next;
                help=help.next;
            }
            System.out.print(first+"\t");
            first=first.next;
            help.next=first;
        }
        System.out.print(first+"\t");
    }

    //打印环形链表
    public void print(){
        if (tail==head){
            System.out.println("链表为空");
        }else {
            Node temp=head.next;
            do {
                System.out.print(temp+"\t");
                temp=temp.next;
            }while (temp!=head.next);
            System.out.println();
        }
    }

    public static void main(String[] args){
        Node head=new Node(-1);
        LoopLinkedList loopLinkedList=new LoopLinkedList(head);
        loopLinkedList.add(new Node(1));
        loopLinkedList.add(new Node(2));
        loopLinkedList.add(new Node(3));
        loopLinkedList.add(new Node(4));
        loopLinkedList.add(new Node(5));
        loopLinkedList.print();
        
        loopLinkedList.joseph(3,2);
    }
}
